#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int l[N], r[N]; // 存树

// 先序遍历
void dfs1(int u)
{
    cout << u << " ";
    if(l[u]) dfs1(l[u]);
    if(r[u]) dfs1(r[u]);
}

// 中序遍历
void dfs2(int u)
{
    if(l[u]) dfs2(l[u]);
    cout << u << " ";
    if(r[u]) dfs2(r[u]);
}

// 后序遍历
void dfs3(int u)
{
    if(l[u]) dfs3(l[u]);
    if(r[u]) dfs3(r[u]);
    cout << u << " ";
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
    }

    dfs1(1); // 先序遍历
    cout << endl;

    dfs2(1); // 中序遍历
    cout << endl;

    dfs3(1); // 后序遍历
    cout << endl;

    return 0;
}